import java.util.Arrays;

/**
 * @author ChenJunhong
 * @date 2018/10/30
 * Description:
 * 插入排序
 *
         */
public class InsertSort {

    public static void insertSort(int[] arr){
        // 表示已经排序的数组的下标，在这个下标之前的数据都已经进行了排序了
        int j;

        // i 代表循环次数，从1开始，因为默认第一个元素是已经排序的
        for (int i = 1; i < arr.length; i++) {
            // 临时变量，获取第i个元素的值
            int tmp = arr[i];

            // 在已经排序的前j个数据中，先从第i个开始，依次跟前一个值进行比较
            // 如果tmp的值比较小，将大元素也就是 arr[j-1] 往后移
            // 额，这里j是不能=0的，=0都TM溢出了 j-1 都小于0了！！
            for(j = i; j > 0 && tmp < arr[j - 1];j--){
                // 将大的元素往后移
                arr[j] = arr[j - 1];
            }
            // 如果没有比tmp小的了，或者j已经是0了，则在第j个位置插入该元素
            arr[j] = tmp;
            System.out.println(Arrays.toString(arr));
        }
    }

    public static void main(String[] args) {
        int[] arr = {34,5,6,3};
        System.out.println(Arrays.toString(arr));
        insertSort(arr);
    }

}
